package com.xyhuo.leetcode.november;

import java.util.*;

/**
 * 子数组的最小值之和
 * https://leetcode.cn/problems/sum-of-subarray-minimums/
 *
 * @time 2023/11/27
 * @desc 抄的官方题解
 */
public class SumSubarrayMins {

//    public static void main(String[] args) {
//        SumSubarrayMins sumSubarrayMins = new SumSubarrayMins();
//        int[] arr = {1, 7, 5, 2, 4, 3, 9};
//        int i = sumSubarrayMins.sumSubarrayMins(arr);
//        System.out.println(i);
//    }

    public int sumSubarrayMins(int[] arr) {
        int length = arr.length;
        int[] dp = new int[length];
        Deque<Integer> deque = new ArrayDeque<>();
        int ans = 0;
        for (int i = 0; i < length; i++) {
            while (!deque.isEmpty() && arr[deque.peek()] > arr[i]) {
                deque.pop();
            }
            int k = deque.isEmpty() ? (i + 1) : (i - deque.peek());
            dp[i] = k * arr[i] + (deque.isEmpty() ? 0 : dp[i - k]);
            ans = (ans + dp[i]) % 1000000007;
            deque.push(i);
        }
        return ans;
//        int length = arr.length;
//        List<List<Integer>> dp = new ArrayList<>();
//        List<Integer> first = new ArrayList<>();
//        first.add(arr[0]);
//        dp.add(first);
//        int result = arr[0];
//        for (int i = 1; i < length; i++) {
//            List<Integer> tmp = new ArrayList<>();
//            tmp.add(arr[i]);
//            result = (result + arr[i]) % 1000000007;
//            List<Integer> lastList = dp.get(i - 1);
//            for (Integer lastVal : lastList) {
//                int val = Math.min(lastVal, arr[i]);
//                tmp.add(val);
//                result = (result + val) % 1000000007;
//            }
//            dp.add(tmp);
//        }
//        return result;


    }
}
